{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Max Increase to Keep City Skyline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxIncreaseKeepingSkyline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #保持城市天际线"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一座由 <code>n x n</code> 个街区组成的城市，每个街区都包含一座立方体建筑。给你一个下标从 <strong>0</strong> 开始的 <code>n x n</code> 整数矩阵 <code>grid</code> ，其中 <code>grid[r][c]</code> 表示坐落于 <code>r</code> 行 <code>c</code> 列的建筑物的 <strong>高度</strong> 。</p>\n",
    "\n",
    "<p>城市的 <strong>天际线</strong> 是从远处观察城市时，所有建筑物形成的外部轮廓。从东、南、西、北四个主要方向观测到的 <strong>天际线</strong> 可能不同。</p>\n",
    "\n",
    "<p>我们被允许为 <strong>任意数量的建筑物 </strong>的高度增加<strong> 任意增量（不同建筑物的增量可能不同）</strong> 。 高度为 <code>0</code> 的建筑物的高度也可以增加。然而，增加的建筑物高度 <strong>不能影响</strong> 从任何主要方向观察城市得到的 <strong>天际线</strong> 。</p>\n",
    "\n",
    "<p>在 <strong>不改变</strong> 从任何主要方向观测到的城市 <strong>天际线</strong> 的前提下，返回建筑物可以增加的 <strong>最大高度增量总和</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/21/807-ex1.png\" style=\"width: 700px; height: 603px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]\n",
    "<strong>输出：</strong>35\n",
    "<strong>解释：</strong>建筑物的高度如上图中心所示。\n",
    "用红色绘制从不同方向观看得到的天际线。\n",
    "在不影响天际线的情况下，增加建筑物的高度：\n",
    "gridNew = [ [8, 4, 8, 7],\n",
    "            [7, 4, 7, 7],\n",
    "            [9, 4, 8, 7],\n",
    "            [3, 3, 3, 3] ]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[0,0,0],[0,0,0],[0,0,0]]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>增加任何建筑物的高度都会导致天际线的变化。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == grid.length</code></li>\n",
    "\t<li><code>n == grid[r].length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 50</code></li>\n",
    "\t<li><code>0 &lt;= grid[r][c] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [max-increase-to-keep-city-skyline](https://leetcode.cn/problems/max-increase-to-keep-city-skyline/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [max-increase-to-keep-city-skyline](https://leetcode.cn/problems/max-increase-to-keep-city-skyline/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]', '[[0,0,0],[0,0,0],[0,0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        row_max = [max(row) for row in grid]\n",
    "        col_max = [max(col) for col in zip(*grid)]\n",
    "        \n",
    "        total_increment = 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                new_height = min(row_max[i], col_max[j])\n",
    "                total_increment += max(0, new_height - grid[i][j])\n",
    "        \n",
    "        return total_increment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "        result = 0\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        rows, cols = [0] * row, [0] * col\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                rows[i] = max(rows[i], grid[i][j])\n",
    "                cols[j] = max(cols[j], grid[i][j])\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                result += max(0, min(rows[i], cols[j]) - grid[i][j])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        rowmax,colmax=[0]*n,[0]*n\n",
    "        for r in range(0,n):\n",
    "            for j in range(0,n):\n",
    "                if grid[r][j]>=colmax[j]:\n",
    "                    colmax[j]=grid[r][j]\n",
    "                if grid[r][j]>=rowmax[r]:\n",
    "                    rowmax[r]=grid[r][j]\n",
    "        sum=0\n",
    "        for r in range(0,n):\n",
    "            for j in range(0,n):\n",
    "                sum += min(rowmax[r],colmax[j])-grid[r][j]\n",
    "        return sum\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "        rowMax = list(map(max, grid))\n",
    "        colMax = list(map(max, zip(*grid)))\n",
    "        \n",
    "        sum=0\n",
    "        for i, row in enumerate(grid):\n",
    "                for j, h in enumerate(row):\n",
    "                   sum+=min(rowMax[i], colMax[j]) - h\n",
    "                   print(min(rowMax[i], colMax[j]) - h)\n",
    "        return sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        \n",
    "        maxIncrease = 0\n",
    "        for r in range(row):\n",
    "            for c in range(col):\n",
    "                minMax = min(max(grid[r]), max([x[c] for x in grid]))\n",
    "                if grid[r][c]<minMax:\n",
    "                    maxIncrease += minMax - grid[r][c]\n",
    "        return maxIncrease\n",
    "    \n",
    "def main():\n",
    "    grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]\n",
    "    num = Solution().maxIncreaseKeepingSkyline(grid)\n",
    "    print(num)\n",
    "    \n",
    "if __name__=='__main__':\n",
    "    main()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        dd = [(0,1), (1,0), (0,-1), (-1,0)]\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j, d):\n",
    "            ii = i + dd[d][0]\n",
    "            jj = j + dd[d][1]\n",
    "            if ii<0 or ii>=n or jj<0 or jj>=m:\n",
    "                return grid[i][j]\n",
    "            return max(grid[i][j], dfs(ii, jj, d))\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                # print(dfs(i, j, 1), end=' ')\n",
    "                # print(min([dfs(i, j, d) for d in range(4)]), end=' ')\n",
    "                ans += min(max(dfs(i,j,0),dfs(i,j,2)), max(dfs(i,j,1),dfs(i,j,3))) - grid[i][j]\n",
    "            # print()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "        y_long = len(grid)\n",
    "        x_long = len(grid[0])\n",
    "        \n",
    "        y_highest = []\n",
    "        for i in range(y_long):\n",
    "            y_highest += [max(grid[i])]\n",
    "        \n",
    "        \n",
    "        T = list(np.transpose(grid))\n",
    "        x_highest = []\n",
    "        for j in range(x_long):\n",
    "            x_highest += [max(T[j])]\n",
    "        \n",
    "        Sum = 0\n",
    "        for i in range(y_long):\n",
    "            for j in range(x_long):\n",
    "                if grid[i][j]!=x_highest[j] and grid[i][j]!=y_highest[i]:\n",
    "                \n",
    "                    Sum += min(x_highest[j],y_highest[i])-grid[i][j]\n",
    "        \n",
    "        return Sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "        import numpy as np\n",
    "        x = np.array(grid)\n",
    "        r = []\n",
    "        t = []\n",
    "        for i in range(x.shape[0]):\n",
    "            r.append(np.max(x[i]))\n",
    "        for i in range(x.shape[0]):\n",
    "            t.append(np.max(x[:, i]))\n",
    "        sumx = 0\n",
    "        for i in range(x.shape[0]):\n",
    "            for j in range(x.shape[0]):\n",
    "                sumx += min(r[i], t[j]) - x[i, j]\n",
    "        return sumx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "        import numpy as np\n",
    "        grid = np.array(grid)\n",
    "        length_row = len(grid)\n",
    "        length_col = len(grid[0])\n",
    "        result = 0\n",
    "        highest_row = []\n",
    "        highest_col = []\n",
    "        for i in range(length_row):\n",
    "            highest_row.append(max(grid[i]))\n",
    "        \n",
    "        for j in range(length_col):\n",
    "            highest_col.append(max(grid[:, j]))\n",
    "        \n",
    "        for i in range(length_row):\n",
    "            max_row = highest_row[i]\n",
    "            for j in range(length_col):\n",
    "                max_col = highest_col[j]\n",
    "                max_add = min(max_row, max_col)\n",
    "                if grid[i, j] < max_add:\n",
    "                    result += max_add - grid[i, j]\n",
    "                    \n",
    "        return result\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [[0]*n for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = min(max(grid[i]), max(grid[s][j] for s in range(m)))\n",
    "        return sum(map(sum, ans))-sum(map(sum, grid))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "        if (not grid or not grid[0]):\n",
    "            return 0\n",
    "        rs_max=[]\n",
    "        cs_max=[]\n",
    "        tmp=np.array(grid)\n",
    "        for r in range(len(tmp)):\n",
    "            rs_max.append(max(tmp[r]))\n",
    "        for c in range(len(tmp[0])):\n",
    "            cs_max.append(max(tmp[:,c]))\n",
    "        #print(rs_max,cs_max)\n",
    "        ans=0\n",
    "        for r in range(len(grid)):\n",
    "            for c in range(len(grid[0])):\n",
    "                if (grid[r][c]<min(cs_max[c],rs_max[r])):\n",
    "                    ans+=min(cs_max[c],rs_max[r])-grid[r][c]\n",
    "                    #grid[r][c]=min(cs_max[c],rs_max[r])\n",
    "        #print(grid)\n",
    "        return ans\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "        grid = np.array(grid)\n",
    "        count = 0\n",
    "        for i in range(grid.shape[0]):\n",
    "            for j in range(grid.shape[1]):\n",
    "                temp = min(max(grid[i]),max(grid.T[j]))\n",
    "                count += temp - grid[i][j]\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "        st = 0\n",
    "        rmax = [max(r) for r in grid]\n",
    "        cmax = [max(c) for c in zip(*grid)]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                st += min(rmax[i],cmax[j]) - grid[i][j]\n",
    "        return st"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "        import numpy as np \n",
    "        grid=np.array(grid)\n",
    "        v=grid.max(axis=0)\n",
    "        h=grid.max(axis=1)\n",
    "        total_height=0\n",
    "        for i in range(len(v)):\n",
    "            for j in range(len(h)):\n",
    "                total_height+=min(v[i],h[j])\n",
    "        return total_height-grid.sum()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "        import numpy as np\n",
    "        heng = np.amax(grid, axis=0)\n",
    "        shu = np.amax(grid, axis=1)\n",
    "        #print(heng)\n",
    "        #print(shu)\n",
    "        count=0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                count+=min(shu[i],heng[j])-grid[i][j]\n",
    "        return count\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "        import numpy as np\n",
    "        C=grid.copy()            #复制\n",
    "        A=[max(x) for x in grid] #左视图\n",
    "        a=np.asarray(grid)       #list转数组\n",
    "        b=np.transpose(a).tolist()    # 数组转置后转list\n",
    "        B=[max(x) for x in b]   #俯视图\n",
    "        for i in range(len(A)):\n",
    "            for j in range(len(B)):\n",
    "                C[i][j]=min(A[i],B[j])\n",
    "        c=np.asarray(C)          #gridNew\n",
    "        D=c-a                    #新-旧\n",
    "        return D.sum()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "        import numpy as np\n",
    "        n = np.array(grid)\n",
    "        k = n.max(axis=1)\n",
    "        p = n.max(axis=0)\n",
    "        s = 0\n",
    "        for i in range(len(grid)):\n",
    "            for t in range(len(grid[i])):\n",
    "                s += (min(k[i], p[t]) - grid[i][t])\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "        import numpy as np\n",
    "        ans=0\n",
    "        a=np.array(grid)\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                max1=max(a[i,:])\n",
    "                max2=max(a[:,j])\n",
    "                ans+=min(max1,max2)-a[i,j]\n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "        # if not grid or not grid[0]:return 0\n",
    "        # list_=np.array(grid)\n",
    "        # length=len(grid)\n",
    "        # r_max,c_max=[0]*length,[0]*length\n",
    "        # for i in range(length):\n",
    "        #     r_max[i]=max(list_[i])\n",
    "        #     c_max[i]=max(list_[:,i])\n",
    "        # res=0\n",
    "        # for i in range(length):\n",
    "        #     for j in range(length):\n",
    "        #         temp=min(r_max[i],c_max[j])\n",
    "        #         res= res +(0 if grid[i][j]>=temp else temp-grid[i][j])\n",
    "        # return res\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "\n",
    "        row_max, col_max = [0 for i in range(row)], [0 for i in range(col)]\n",
    "        res = [[0 for i in range(col)] for j in range(row)]\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                row_max[i] = max(row_max[i], grid[i][j])\n",
    "                col_max[j] = max(col_max[j], grid[i][j])\n",
    "        res = 0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                res += abs(grid[i][j] - min(row_max[i],col_max[j]))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "        grid = np.array(grid)\n",
    "        counter = 0\n",
    "        for i in range(grid.shape[0]):\n",
    "            for j in range(grid.shape[1]):\n",
    "                counter += min(max(grid[:,j]), max(grid[i,:])) - grid[i,j]\n",
    "\n",
    "        return counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "        import numpy as np\n",
    "        grid1=np.array(grid,dtype=int)\n",
    "        max_vertical=np.max(grid1, axis=0)\n",
    "        max_horizontal=np.max(grid1, axis=1)\n",
    "        n=len(grid)\n",
    "        sum_all=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]!=max_horizontal[i] and grid1[i][j]!=max_vertical[j]:\n",
    "                    sum_all=sum_all+min(max_horizontal[i],max_vertical[j])-grid[i][j]\n",
    "        \n",
    "        \n",
    "        sum_all=int(sum_all)\n",
    "        return sum_all\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid) -> int:\n",
    "        grid_mat = np.array(grid)\n",
    "        dictR = {}\n",
    "        dictC = {}\n",
    "        N = grid_mat.shape[0]\n",
    "        ii = 0\n",
    "        while ii < N:\n",
    "            dictR[ii] = max(grid_mat[ii,:]);\n",
    "            dictC[ii] = max(grid_mat[:,ii]);\n",
    "            ii += 1;\n",
    "        \n",
    "        ii = 0;\n",
    "        sum = 0;\n",
    "        for item in grid_mat.flatten():\n",
    "            row = int(ii/N);\n",
    "            col = int(ii%N);\n",
    "            Max = min(dictR[row],dictC[col]);\n",
    "            sum = int(Max) - int(item) + sum;\n",
    "            ii += 1;\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    \r\n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\r\n",
    "        import numpy\r\n",
    "        row = []\r\n",
    "        for i in range(0, len(grid)):\r\n",
    "            row.append(max(grid[i]))\r\n",
    "        grid_t = numpy.transpose(grid)\r\n",
    "        clo = []\r\n",
    "        for i in range(0, len(grid_t)):\r\n",
    "            clo.append(max(grid_t[i]))\r\n",
    "        result = 0\r\n",
    "        for i in range(0, len(grid)):\r\n",
    "            for j in range(0, len(grid[i])):\r\n",
    "                result += min(row[i], clo[j]) - grid[i][j]\r\n",
    "        return int(result)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from numpy import matrix\n",
    "class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "        N_list=[max(l) for l in grid]\n",
    "        W_list=[max(l) for l in matrix(grid).T.tolist()]\n",
    "        ans=0;n=len(grid);m=len(grid[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                min_num=min(N_list[i],W_list[j])\n",
    "                if grid[i][j]<min_num:\n",
    "                    ans+=min_num-grid[i][j]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    # def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "    #     grid=np.array(grid)\n",
    "    #     res=0\n",
    "    #     for i in range(len(grid)):# 第i行\n",
    "    #         for j in range(len(grid[0])):#第j列\n",
    "    #             res += min(max(grid[i]),max(grid[:,j]))-grid[i][j]\n",
    "    #     return int(res)\n",
    "    #     # 大佬的\n",
    "    #     class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "        rowsMax, colsMax = [max(g) for g in grid], [max(z) for z in zip(*grid)]\n",
    "        return sum(min(rowsMax[i], colsMax[j]) - grid[i][j] for i in range(len(grid)) for j in range(len(grid[0])))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:\n",
    "        import numpy as np\n",
    "        arr = np.array(grid)\n",
    "        row = [max(ns) for ns in grid]\n",
    "        col = [max(cs) for cs in arr.T]\n",
    "        \n",
    "        inhens = np.zeros(arr.shape)\n",
    "\n",
    "        r, c = arr.shape\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                inhens[i, j] = min(row[i], col[j])\n",
    "        \n",
    "        return int((inhens - arr).sum())\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
